1. Field of the Invention
This invention pertains to computer data compression technology and computer printer technology. More specifically, this invention pertains to the addition of margin white space to and then compression of bit map images in a printer, and storing the compressed images in bands of memory for later use by the printer.
2. Description of the Related Art
Technology associated with printers and printing has ridden the tide of the rapid advances of computer technology in general. From the days of the daisy wheel and the nine pin dot matrix printers, we have now come to an era of affordable laser, ink jet, and even color high resolution printing. As the resolutions and corresponding print qualities have risen dramatically, so have the amounts of memory required to drive these printers. Multi-megabyte memory configurations are becoming more common as the resolutions rise.
For example, in monochrome laser printing an image is typically rendered at 300 dots per inch, requiring nearly one megabyte of random access memory for a letter size page. This same image rendered at 600 dots per inch results in a four-fold increase in the required memory, or approximately four megabytes. Higher resolution is not the only cause of increasing memory demands. Color or gray scale images typically require 2 to 32 bits of information for each pixel of the rendered bit image. A letter sized image rendered at 600 dots per inch using 32 bits of color information would require not four megabytes of memory but rather 128 megabytes of memory. The cost of more memory is passed to the consumer either in the initial price of the product or as the cost of an optional memory upgrade.
One development in the field of high resolution printing has involved the transmission of images from the host computer to the printer itself. The transmission of an entire page in a discrete bit image, or rasterized, format created two serious problems as resolutions rose. First, the printer and the host computer were often linked by a relatively slow serial data path, and the transmission of an entire page in rasterized, or bit image, form could lead to unacceptably slow transmission times because of this bottleneck. Second, as resolutions increased and more memory was required to hold an entire rasterized page, it became inefficient to generate that rasterized page in the memory of the host computer itself. Many host computers did not even contain one megabyte of memory, and as that is the amount of memory typically needed for a letter size page, such rasterization was not feasible.
Partially in response to these problems, page description languages were developed. Page description languages describe pages as a group of graphical and textural objects rather than as bit images. For example, a circle might be represented by a data structure giving a center location and a radius. This object oriented approach can lead to far more efficient representation of graphical and textual data. The memory needed to store a bit image is a function of the page size, pixel density, and number of bits of information per pixel. Memory requirements for a set of page description language commands describing a page, on the other hand, are typically proportional to the complexity of the page itself. A very simple page requires few commands and correspondingly little memory to store, while a more complex page requires more memory. For all but the most complex pages, the amount of memory required to store the associated page description language commands is typically less than the amount required to store the corresponding rasterized page image.
The lower memory requirements led to shorter transmission times to the printer. Page description languages also facilitated page generation "on the fly" rather than storing all of the page at one time. This in turn required less memory usage by the host computer. Once the command to generate a circle had been sent, for example, it need not be stored in the host computer memory but could instead be discarded.
An application program can easily create page description language output as all it need do is generate the required "commands" in that language. Then, that page description language text is transmitted to the printer, where an interpreter/rasterizer interprets the codes of the page description language text and rasterizes the page represented by those codes into a bit image. In other words, the interpreter/rasterizer translates the page description language codes into a bit image of the page. That bit image is then stored in the printer memory rather than the host computer memory.
Page description languages further allow for a single software interface to be used with a variety of hardware platforms. A printer's resolution may be lower or higher, the page size may be larger or smaller, but this can all be handled in the implementation of the interpreter/rasterizer that converts the page description language code to a bit image. Thus, the host computer need not know the specifics of the hardware that the interpreter/rasterizer drives.
These page description languages are very well known and include Postscript and Postscript Level 2 by Adobe Systems Incorporated and PCL 5. The interpreter/rasterizer is typically run on its own microprocessor; for example, the 68000 series by Motorola, Inc. or the Am29000 series by Advanced Micro Devices, Inc., can execute the programmed interpreter/rasterizer.
In practice, an application program or the system software of a host computer generates the page description language code for a page and then transmits that code to the printer. There, the software in the interpreter/rasterizer interprets the page description language code, converting the code into a bit image for printing by the print engine. The interpreter/rasterizer will have an associated random access memory of arbitrary size for use as storage for the rasterized bit image, for working memory, for storing subsequent pages, for storing font images, or for other typical memory uses of an interpreter/rasterizer. Typically, the rasterized image will be stored in bands, with multiple bands per page, which can be retrieved for transmission to the print engine and discarded when no longer needed.
Some page description languages do provide for compression of the page description language code itself. Before transmission, the code is compressed using one of a number of well known compression algorithms, and then when received by the printer that code is decompressed. This allows for shorter transmission times, as less data is being transmitted to convey the same amount of information.
Data compression techniques are very well known in the computing field. For example, a class of algorithms known as Lempel-Ziv 77, or LZ77, is widely used for adaptive lossless data compression. Another class known as LZ78 is now more commonly used, but the LZ77 class has unique features that make it particularly suitable to some applications. These algorithms are well known in the art, and a good overview is provided in Ross N. Williams, An Extremely Fast Ziv-Lempel Data Compression Algorithm, DCC '91 Data Compression Conference 362 (James A. Storer & John H. Reif eds., 1991).
In the past, Lempel-Ziv 77 algorithms have had drawbacks that led to inefficiency. For example, those algorithms typically stopped compressing towards the end of a source block. Further, those algorithms typically did not initialize the hash table they used that pointed to data that had been previously compressed. This caused a loss of speed and efficiency when first compressing the data.
The interpreter/rasterizer's use of its random access memory is one area of printer technology ripe for improvement. While page description languages have been invaluable in the generation and transmission of pages, the interpreter/rasterizer must still generate and store a rasterized image of a page in its own memory. As seen above, the memory requirements for a full rasterized page can be enormous.
Developers have used various techniques to reduce these memory requirements within the printer itself. For example, very high end laser printers use a start/stop technique in which they reduce their memory requirements by printing a small section of the page, stopping the print process while the next section of the page is rasterized into memory, and then restarting the print process, repeating these steps until done. These machines typically print at very high resolutions and are quite complex mechanically. In a technique used by PCL 5, the page description language codes are sequenced such that those commands pertaining to the top of the page are placed in the beginning of the source code file and those pertaining to the bottom of the page are placed at the end. The printer is then started and the printer processor that renders the bit map image a band at a time "races" the print engine, or the part of the printer that does the actual printing, by attempting to interpret the codes and render the image at least as fast as the print engine can print the rendered image. This technique, however, usually fails on complex pages, and the user must install more memory to print anything but very simple images.
One area in which current printers lose efficiency in their use of their internal memories is in the storage of margin white space. Printers typically store the white space representing the left and right margins on a page even when the logical margin is larger than the physical margin required by the print engine. This is in part because of how an interpreter/rasterizer transmits data to the print engine. The print engine typically expects the interpreter/rasterizer to transmit a full scan line of data to the print engine. A scan line is simply the memory representation of one row of the printed bit image. This scan line, however, is physically typically of a fixed number of bits, that number being set by the requirements of the print engine. Logically, however, an interpreter/rasterizer need only store the scan line data up to the beginning of the right margin white space. This follows from the manner in which print engines physically function; when the print engine receives nothing, it leaves the corresponding bit white. Thus, the interpreter/rasterizer can simply send nothing to the print engine at the end of the scan line, and therefor need not store anything.
Interpreters/rasterizers typically include any logical margin white space at the front of each scan line. This logical margin white space, when added to the physical margin necessitated by the print engine, forms the full margin. As each page will have a fixed logical margin, however, storage of this margin white space is very inefficient.
Thus, it would be desirable to improve the efficiency of the memory usage by the interpreter/rasterizer in the printer itself. More specifically, it would be desirable if less memory were required to store a bit image.